package 动态规划;

import java.util.*;

/**
 * @description:
 * @author: ywk
 * @date: 2021-01-17
 */
public class 最长递增子序列 {
    //1:动态规划
    public static int longestIncrease(int[] arr) {
        int[] nums = new int[arr.length];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (arr[i] > arr[j]) {
                    nums[i] = nums[j] + 1;
                    break;
                }
            }
        }
        int max = 0;
        for (int num : nums) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }

    //2.动态规划和二分法,与信封嵌套问题类似
    /* 返回 nums 中 LIS 的⻓度 */
    public static int[] LIS(int[] nums) {
        int piles = 1, n = nums.length;
        int[] dp = new int[n];
        int[] top = new int[n];
        top[0] = nums[0];
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            // 要处理的扑克牌
            int poker = nums[i];
            if (top[piles - 1] < nums[i]) {
                top[piles++] = poker;
                dp[i] = piles;
            } else {
                int left = 0, right = piles;
                // ⼆分查找插⼊位置
                while (left < right) {
                    int mid = (left + right) / 2;
                    if (top[mid] >= poker)
                        right = mid;
                    else
                        left = mid + 1;
                }
                top[left] = poker;
                dp[i] = left + 1;
            }
        }
        // 牌堆数就是 LIS ⻓度
        int[] res = new int[piles];
        for (int i = n - 1; i >= 0; i--) {
            if (dp[i] == piles)
                res[--piles] = nums[i];
        }
        return res;
    }


    public static void main(String[] args) {
      Arrays.stream(LIS(new int[]{0, 4, 5, 1, 2, 4, 5})).forEach(e-> System.out.println(e));

    }
}
